package leetcode;

import java.util.ArrayList;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class PathSum {

	public static void main(String[] args) {
		PathSum pathSum = new PathSum();
		int[] pre = {5,4,11,7,2,8,13,4,5,1};
		int[] in = {7,11,2,4,5,13,8,5,4,1};
		TreeNode node = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		System.out.println(pathSum.pathSum(node, 22));
	}
	
	//找到从根节点到叶结点是否有和为sum的路径
	public boolean hasPathSum(TreeNode root, int sum) {
		int curSum = 0;
		boolean find = false;
		if(root == null){
			return find;
		}
		find = realHasPathSum(root, sum, curSum);
//		while(!stack.isEmpty()){
//			TreeNode node = stack.peek();
//			if(node.left != null){
//				stack.add(node.left);
//				curSum += node.left.val;
//			}
//			if(node.right != null){
//				stack.add(node.right);
//				curSum += node.right.val;
//			}
//			if(node.left == null && node.right == null){
//				if(curSum == sum){
//					return true;
//				}
//				else {
//					curSum -= node.val;
//					stack.pop();
//				}
//			}
//		}
		return find;
	}
	
	public boolean realHasPathSum(TreeNode node, int sum, int curSum){
		if(node == null){
			return false;
		}
		boolean isFind = false;
		curSum += node.val;
		System.out.println("curSUm " + curSum + "node.val" + node.val);
		if(node.left == null && node.right == null){
			if(curSum == sum){
				return true;
			}else {
//				curSum -= node.val;
				return false;
			}
		}
		if (node.left != null) {
			isFind = realHasPathSum(node.left, sum, curSum);
		}
		if (!isFind) {
			if (node.right != null) {
				isFind = realHasPathSum(node.right, sum, curSum);
			}
		}
		return isFind;
	}
	
	//返回所有路径
	
	public static ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
		ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		realFind(lists, list, 0, root, sum);
		return lists;
	}

	public static void realFind(ArrayList<ArrayList<Integer>> lists,
			ArrayList<Integer> list, int curSum, TreeNode node, int target) {
		if (node == null) {
			return;
		}
		curSum += node.val;
		list.add(node.val);
		if (node.left == null && node.right == null) {
			if (curSum == target) {
				lists.add(new ArrayList<Integer>(list));
				return;
			} else {
				return;
			}
		}
		if (node.left != null) {
			realFind(lists, list, curSum, node.left, target);
			list.remove(list.size() - 1); // 移除掉最后一个元素
		}
		if (node.right != null) {
			realFind(lists, list, curSum, node.right, target);
			list.remove(list.size() - 1); // 移除掉最后一个元素
		}
	}
	
	
	private int res = 0;
	
	//可以不用从根节点开始，但是必须是向下的,也不用一定要到叶子结点
	//好吧，这个竟然AC了，感觉时间复杂度很大啊
	public int pathSum_3(TreeNode root, int sum) {
		res = 0;
        if(root == null){
        	return 0;
        }
        realFind_3(0, root, sum);
        res += pathSum_3(root.left, sum);
        res += pathSum_3(root.right, sum);
        return res;
    }
	
	public void realFind_3(int curSum, TreeNode node, int target) {
		if (node == null) {
			return;
		}
		curSum += node.val;
		if (curSum == target) {
			res++;
		}
		if (node.left != null) {
			realFind_3(curSum, node.left, target);
		}
		if (node.right != null) {
			realFind_3(curSum, node.right, target);
		}
	}
	
	//int[0]表示的值，int[1]表示相等的个数
//	public int[] realFind_3(TreeNode root, int curSum, int target){
//		int[] res = new int[2];
//		if(root == null){
//			return res;
//		}
//		if(root.left == null && root.right == null){
//			if(root.val == target){
//				res[1] = 1;
//			}
//			res[0] = root.val;
//			return res;
//		}
//		int[] leftValue;
//		int[] rightValue;
//		if(root.left != null){
//			leftValue = realFind_3(root.left, curSum, target);
//		}
//		if(root.right != null){
//			rightValue = realFind_3(root.right, curSum, target);
//		}
////		if(leftValue)
////		res++;
//	}
}
